package com.hdu.other.dp.shuweiDp;


public class lc2719 {
    class Solution {
        int max;
        int min;
        char[] nums;
        int len = 0;
        int mod = 1000000007;
        int[][][] dp;
        public int count(String num1, String num2, int min_sum, int max_sum) {
            max = max_sum;
            min = min_sum;
            nums = num2.toCharArray();
            len = num2.length();
            refreshDp();
            int ans = f(0, 0, 0);
            nums = num1.toCharArray();
            len = num1.length();
            refreshDp();
            ans = (ans - f(0, 0, 0) + mod) % mod;
            if (check())
            {
                ans = (ans + 1) % mod;
            }
            return ans;
        }

        int f(int i, int sum, int free)
        {
            if (sum > max)
            {
                return 0;
            }
            if (sum + (len - 1 - i + 1) * 9 < min)
            {
                return 0;
            }
            if (i == len)
            {
                return 1;
            }
            if (dp[i][sum][free] != -1)
            {
                return dp[i][sum][free];
            }
            int cur = nums[i] - '0';
            int ans = 0;
            if (free == 0)
            {
                for (int pick = 0; pick < cur; pick++)
                {
                    ans = (ans + f(i + 1, sum + pick, 1)) % mod;
                }
                ans = (ans + f(i + 1, sum + cur, 0)) % mod;
            }
            else
            {
                for (int pick = 0; pick <= 9; pick++)
                {
                    ans = (ans + f(i + 1, sum + pick, 1)) % mod;
                }
            }
            dp[i][sum][free] = ans;
            return ans;
        }

        void refreshDp() {
            dp = new int[len + 1][max + 1][2];
            for (int i = 0; i < len + 1; i++) {
                for (int j = 0; j < max + 1; j++) {
                    for (int k = 0; k < 2; k++) {
                        dp[i][j][k] = -1;
                    }
                }
            }
        }

        boolean check() {
            int sum = 0;
            for (int i = 0; i < nums.length; i++) {
                sum += nums[i] - '0';
            }
            return sum >= min && sum <= max;
        }


    }
}
